#include <stdio.h>
#include <string.h>
#include <stdlib.h>


/*生成KMP算法中的next数组*/
void getnext(char* strs,int length,int* next)
{   
    next[1]=0;
    int i=1,j=0;
    while(i<length)
    {
        if(j==0||strs[i]==strs[j])
        next[++i]=++j;
        else
        j=next[j];
    }
}

/*KMP算法主体*/
int kmp(char* str1,char* str2)
{
    int len1=strlen(str1);
    int len2=strlen(str2);                //计算两个字符串的长度备用

    int* next=(int*)malloc(sizeof(int)*len2);   //为NEXT数组开辟与子串一样大的内存空间

    getnext(str2,len2,next);                 //调用GETNEXT函数，生成next数组


    if(len1==0&&len2==0||len2==0) return 0;                 //当str1与str2都为空，或str2为空时，直接返回
    else if(len1==0||len2>len1) return -1;                  //当str1为空，或者str2比str1长时

    int i=0;
    int j=0;

   for(int i = 0,j = 0;i<len1;i++){
        while(j > 0 && str1[i] != str2[j]) j = next[j];
        if(str1[i] == str2[j])j++;
        if(j == len2)return i-len2+1;
    }
    return -1;
}


// while (i < len1 && j < len2)						//当arr1和arr2都没走到尽头
// 	{
// 		if (arr1[i] == arr2[j])
// 		{
// 			i++;
// 			j++;
// 		}
// 		else
// 		{
// 			j = Next[j];						        //当主串与子串不同时j回溯到 
//                                                         //Next[j]，i不用回溯
// 		}
// 	}
// 	if (j >= len2)
// 		return i - j;							        //如果子串走到尽头，代表找到了返回 
//                                                         //开始匹配时的位置
// 	return -1;				
